High Efficiency Video Coding (HEVC) is a new coding standard that has been developed in recent years. In the High Efficiency Video Coding (HEVC) system, the fixed-size macroblock of H.264/AVC is replaced by a flexible block, named coding unit (CU). Pixels in the CU share the same coding parameters to improve coding efficiency. A CU may begin with a largest CU (LCU), which is also referred as coded tree unit (CTU) in HEVC. In addition to the concept of coding unit, the concept of prediction unit (PU) is also introduced in HEVC. Once the splitting of CU hierarchical tree is done, each leaf CU is further split into one or more prediction units (PUs) according to prediction type and PU partition.
Along with the High Efficiency Video Coding (HEVC) standard development, the development of extensions of HEVC has also started. The HEVC extensions include screen content coding (SCC). Due to specific characteristics of screen contents, coding tools have been developed and demonstrate significant gains in coding efficiency. Among them, the color index coding (a.k.a. major color based coding) techniques represent block of pixels using indices to the palette (major colors), and encode the palette and the indices by exploiting spatial redundancy. While the total number of possible color combinations is huge, the number of colors in an area of picture is usually very limited for typical screen contents. Therefore, the color index coding becomes very effective for screen content materials. Related key color index coding techniques are briefly reviewed as follows.
Major-Color-Based Screen Content Coding
The major-color-based screen content coding is disclosed in JCTVC-O0108 (Guo, et al., “RCE4: Test1. Major-color-based screen content coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 16th Meeting: San Jose, Calif., USA, Jan. 9-17, 2014, Document: JCTVC-P0108). Major-color-based screen content coding is performed on a CU basis. The encoding process is as follows:
Selecting Major Colors
A very simple but efficient histogram based algorithm is used to classify the pixels. In specific, the most significant L peak values in the histogram are selected as major colors, and the pixel values that are close to a major color will be quantized to the major color. Other pixels which do not belong to any major color sets are escape pixels, which will also be quantized before coding. For lossless coding, both of the quantization processes are not used. For each pixel, a color index is assigned to indicate which color set it belongs to. The color index may also be referred as an index for convenience when the term will not cause any confusion. If L major colors are used, the values of major colors 0 to (L−1) are signaled for the set of L major colors and the value of major color N is signaled for the escape pixel set.
Encoding the Color Index
After classification, the pixels of a block can be converted into color indices according to the major color set selected. A predictive coding method is applied to the indices, where a pixel line can be predicted by three different modes, including horizontal mode (i.e., copy index mode), vertical mode (i.e., copy above mode) and normal mode (i.e., escape mode).
Copy Index Mode
In copy index mode, starting from the first pixel, one or more consecutive indices are copied from the first pixel. The index of the first pixel is signaled.
Copy Above Mode
In this mode, one or more consecutive indices are copied from above pixel line.
Escape Mode
When an escape pixel is encountered (signaled by the largest index in major color set), its corresponding pixel value is coded right after the index. There may be more than 1 escape pixels and in different color values in the CU. For different escape pixel locations, the pixel values of escape pixels may be different.
Palette Mode Coding
A palette-based coding technique is disclosed in JCTVC-P0198 (Guo et al., “RCE4: Results of Test 2 on Palette Mode for Screen Content Coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 16th Meeting: San Jose, Calif., USA, Jan. 9-17, 2014, Document: JCTVC-P0198). The palette-based coding is performed on a CU basis. The encoding process is as follows:
Transmission of the palette: the palette size is first transmitted followed by the palette elements. The maximum palette size is set to 24.
Transmission of pixel values: the pixels in the CU are encoded in a raster scan order. For each position, a flag is first transmitted to indicate whether the “run mode” (i.e., “copy-index mode” in this disclosure) or “copy-above mode” is being used.
“Run mode”: In “run mode” (i.e., “copy-index mode” in this disclosure), a palette index is first signaled followed by “palette_run” (e.g., M). No further information needs to be transmitted for the current position and the following M positions as they have the same palette index as signaled. The palette index (e.g., i) is shared by all three color components, which means that the reconstructed pixel values are (Y, U, V)=(paletteY[i], paletteU[i], paletteV[i]) if the color space corresponds to YUV.
“Copy-above mode”: In “copy-above mode”, a value “copy_run” (e.g., N) is transmitted to indicate that for the following N positions (including the current one), the palette index is equal to the palette index of the one that is at the same location in the row above.
Transmission of residue: the palette indices transmitted are converted back to pixel values and used as the prediction. Residue information is transmitted using HEVC residue coding and is added to the prediction for the reconstruction.
Copy from Previous Row Above
Another index coding mode, called “copy from previous row”, is disclosed in JCTVC-R0202 (Zou et al., “Non-SCCE3: Copy from previous row mode for palette coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, Japan, Jun. 30-Jul. 9, 2014, Document: JCTVC-R0202). This method enables to copy pixels from previously coded rows beyond the row above in the current CU. To achieve a better coding efficiency, all the previous coded rows are available as reference according to JCTVC-R0202. Accordingly, this mode is called “copy from previous row”. This mode is added in the available palette mode candidate list. The row index information is coded when the current string chooses “copy from previous row” mode. The row index is coded using truncated binary codeword. Basically, a shorter codeword is designed for the row which is near to the current row. Similar to other modes, the matching length is coded in the bitstream.
In JCTVC-00108 and JCTVC-P0198, similar palette based coding methods are disclosed. These references use slightly different terms for related parameters. The term “palette” in JCTVC-00108 and the term “major color sets” in JCTVC-P0198 are referred as “major color table” in this disclosure. The term “palette index” in JCTVC-00108 and the term “color index” in JCTVC-P0198 are referred as “color index” in this disclosure. The color indices related to the current coding unit are referred as “index map”.
For a run of indices in the index map, there are several elements that need to be signaled, including:                1) Run type: either it is a copy above run or a copy index run.        2) Palette index: in a copy index run, it is used to signal what index is used for this run.        3) Run length: the length of this run for both copy above and copy index type.        4) Escape pixel: if there N (N>=1) escape pixels in the run, the N pixel values need to be signaled for these N escape pixels.        
In JCTVC-T0065 (Karczewicz, et al., Non CE1: Grouping Palette Indices At Front, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 20th Meeting: Geneva, CH, 10-18 Feb. 2015, Document: JCTVC-T0065), a syntax signaling is disclosed, where all the palette indices are grouped together. The number of palette indices is signaled first, following by the palette indices.
It is co-pending PCT Patent Application (Serial No. PCT/CN2015/094410, filed on Nov. 12, 2015), a syntax signaling method by grouping all the escape is disclosed by some common inventors of the current application.
The coding of palette index run type and run length in the HEVC Screen Content Coding specification (Joshi, et al., High Efficiency Video Coding (HEVC) Screen Content Coding: Draft 2, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 19th Meeting: Strasbourg, FR, 17-24 Oct. 2014, Document: JCTVC-S1005) is as follows:
TABLE 1Noteif( indexMax > 0 && scanPos > = nCbS && palette_run_type_flag[ xcPrev ][ ycPrev ] ! = COPY_ABOVE_MODE ) {palette_run_type_flag[ xC ][ yC ](1-1) }if( palette_run_type_flag[ xC ][ yC ] = =COPY_INDEX_MODE && adjustedIndexMax > 0)palette_index_idc(1-2)if( indexMax > 0 ) {maxPaletteRun = nCbS * nCbS − scanPos − 1if( maxPaletteRun > 0 ) {palette_run_msb_id_plus1(1-3)if( palette_run_msb_id_plus1 > 1 )palette_run_refinement_bits(1-4)}
As shown in Table 1, syntax elements for the palette run type (i.e., palette_run_type_flag[xC][yC]) and palette index (i.e., palette_index_idc) are incorporated for each occurrence as indicated by Notes (1-1) and (1-2). Two syntax elements palette_run_msb_id_plus1 and palette_run_refinement_bits are used to signal the run length corresponding to a MSB (most significant bit) part and refinement part respectively as indicated by Notes (1-3) and (1-4) in Table 1.
Palette Table Signaling
In the reference software of screen content coding (SCC) standard, SCM-2.0 (Joshi et al., Screen content coding test model 2 (SCM 2), Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, JP, July 2014, Document No.: JCTVC-R1014), an improved palette scheme is integrated in JCTVC-R0348 (Onno, et al., Suggested combined software and text for run-based palette mode, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, JP, July 2014, Document No.: JCTVC-R0348). The palette table of previous palette-coded CU is used as a predictor for current palette table coding. In palette table coding, the current palette table is signaled by choosing which palette colors in the previous coded palette table (palette predictor) are reused, or by transmitting new palette colors. The size of the current palette is set as the size of the predicted palette (i.e., numPredPreviousPalette) plus the size of the transmitted palette (i.e., num_signaled_palette_entries). The predicted palette is a palette derived from the previously reconstructed palette coded CUs. When coding the current CU as a palette mode, those palette colors that are not predicted using the predicted palette are directly transmitted in the bitstream (i.e., signaled entries).
An example of palette updating is shown as follows. In this example, the current CU is coded as palette mode with a palette size equal to six. Three of the six major colors are predicted from the palette predictor (numPredPreviousPalette=3) and three are directly transmitted through the bitstream. The transmitted three colors can be signaled using the exemplary syntax shown below.
num_signalled_palette_entries = 3for( cIdx = 0; cIdx < 3; cIdx++ ) // signal colors for different components  for( i = 0; i < num_signalled_palette_entries; i++ )  palette_entries[ cIdx ][ numPredPreviousPalette +i ]
Since the palette size is six in this example, the palette indices from 0 to 5 are used to indicate the major color entries in the palette color table. The 3 predicted palette colors are represented with indices 0 to 2. Accordingly, three new palette entries are transmitted for indexes 3 through 5.
In SCM-2.0, if the wavefront parallel processing (WPP) is not applied, the palette predictor table is initialized (reset) at the beginning of each slice or at the beginning of each tile. If the WPP is applied, the last coded palette table is not only initialized (reset) at the beginning of each slice or at the beginning of each tile, but also initialized (reset) at the beginning of each CTU row.
In the HEVC SCC draft, a CU level flag “palette_escape_val_present_flag” is signaled when the palette size of the current Cs is greater than 0. If this flag is true, the use of escape pixels is enabled for this CU. One example of syntax table is shown in Table 2.
TABLE 2Noteif( palette_escape_val_present_flag ) {(2-1)sPos = 0while( sPos < nCbS * nCbS ) {xC = x0 + travScan[ sPos ][ 0 ]yC = y0 + travScan[ sPos ][ 1 ]if( PaletteIndexMap[ xC ][ yC ] = = MaxPaletteIndex ) {(2-2)for( cIdx = 0; cIdx < numComps; cIdx++ )if( cIdx = = 0 | |( xR % 2 = = 0 && yR % 2 = = 0 &&ChromaArrayType = = 1 ) | |( xR % 2 = = 0 &&ChromaArrayType = = 2 ) | |ChromaArrayType = = 3 ) {palette_escape_val(2-3)PaletteEscapeVal[ cIdx ][ xC ][ yC] = palette_escape_val}}sPos++}}
In Table 2, if palette_escape_val_present_flag, as indicated by Note (2-1) is equal to 1, it indicates that at least one escape value exists for the CU. As mentioned before, the escape index corresponds to the largest palette index plus 1 (i.e., MaxPaletteIndex as indicated by Note (2-2)). In this case, the escape value is parsed from the bitstream as indicated by Note (2-3).
In palette coding, certainly relationship/restriction among various run modes can be utilized to improve coding efficiency. For example:                if the previous pixel is in a copy above run, then the current index should not be the same as its above pixel; and        if the previous pixel is in a copy index run, then the current index should not be the same as its previous pixel.        
Therefore, the number of possible index values can be reduced by 1. This technique is called “redundancy removal”. The corresponding semantics is as follows. The variable PaletteIndexMap[xC][yC] specifies a palette index, which is an index to the array represented by CurrentPaletteEntries. The array indices xC and yC specify the location (xC, yC) of the sample relative to the top-left luma sample of the picture. The value of PaletteIndexMap[xC][yC] shall be in the range from 0 to MaxPaletteIndex, inclusive.
The variable adjustedRefPaletteIndex is derived as follows:
 adjustedRefPaletteIndex = MaxPaletteIndex + 1if( PaletteScanPos > 0 ) {   if( palette_run_type_flag[xcPrev][ycPrev] !=    COPY_ABOVE_MODE ) {    xcPrev = xC + travScan[PaletteScanPos − 1][0]    ycPrev = yC + travScan[PaletteScanPos − 1][1]    adjustedRefPaletteIndex =     PaletteIndexMap[xcPrev][ycPrev](7-79)   }   else    adjustedRefPaletteIndex = PaletteIndexMap[xC][yC − 1]
When PaletteSampleMode[xC][yC] is not equal to COPY_ABOVE_MODE, the variable CurrPaletteIndex is derived as follows:
 If MaxPaletteIndex is equal to 0  CurrPaletteIndex = 0Otherwizse,  CurrPaletteIndex = PaletteIndexIdc[CurrNumIndices]  if( CurrPaletteIndex >= adjustedRefPaletteIndex )   CurrPaletteIndex + = 1
Palette Index Map Scan Order
In SCM-3.0 palette mode coding, the traverse scan is used for index map coding as shown in FIG. 1. FIG. 1 shows a traverse scan for an 8×8 block. In traverse scan, the scan for even rows is from left to right, and the scan for odd rows is from tight to left when the scanning order is horizontal. The traverse scan can also be applied in the vertical direction, where the scan is from top to bottom for even columns and from bottom to top for odd columns. The traverse scan is applied for all block sizes in palette mode.
SPS And PPS Syntax Related to Luma and Chroma Component
In the SPS (Sequence Parameter Set) and PPS (Picture Parameter Set) syntax tables for HEVC, there are some syntax elements related to luma and chroma components. However, for a monochrome video coding system, there are only one color component and these syntax elements related to the chroma component may have some redundancy. Some related syntax elements and their corresponding semantics are shown below.
SPS Related Syntax Elements and Semantics
bit_depth_luma_minus8 specifies the bit depth of the samples of the luma array BitDepthY and the value of the luma quantization parameter range offset QpBdOffsetY as follows:BitDepthY=8+bit_depth_luma_minus8, andQpBdOffsetY=6*bit_depth_luma_minus8,where bit_depth_luma_minus8 shall be in the range of 0 to 8, inclusive.
bit_depth_chroma_minus8 specifies the bit depth of the samples of the chroma arrays BitDepthC and the value of the chroma quantization parameter range offset QpBdOffsetC as follows:BitDepthC=8+bit_depth_chroma_minus8, andQpBdOffsetC=6*bit_depth_chroma_minus8,where bit_depth_chroma_minus8 shall be in the range of 0 to 8, inclusive.
pcm_sample_bit_depth_luma_minus1 specifies the number of bits used to represent each of PCM sample values of the luma component as follows:PcmBitDepthY=pcm_sample_bit_depth_luma_minus1+1,where the value of PcmBitDepthY shall be less than or equal to the value of BitDepthY.
pcm_sample_bit_depth_chroma_minus1 specifies the number of bits used to represent each of PCM sample values of the chroma components as follows:PcmBitDepthC=pcm_sample_bit_depth_chroma_minus1+1,where the value of PcmBitDepthC shall be less than or equal to the value of BitDepthC. When ChromaArrayType is equal to 0, pcm_sample_bit_depth_chroma_minus1 is not used in the decoding process and decoders shall ignore its value.
PPS Related Syntax Elements and Semantics
diff_cu_qp_delta_depth specifies the difference between the luma coding tree block size and the minimum luma coding block size of coding units that convey cu_qp_delta_abs and cu_qp_delta_sign_flag. The value of diff_cu_qp_delta_depth shall be in the range of 0 to log2_diff_max_min_luma_coding_block_size, inclusive. When not present, the value of diff_cu_qp_delta_depth is inferred to be equal to 0. The variable Log2MinCuQpDeltaSize is derived as follows:Log2MinCuQpDeltaSize=CtbLog2SizeY−diff_cu_qp_delta_depth.
pps_cb_qp_offset and pps_cr_qp_offset specify the offsets to the luma quantization parameter Qp′Y used for deriving Qp′Cb and Qp′Cr, respectively. The values of pps_cb_qp_offset and pps_cr_qp_offset shall be in the range of −12 to +12, inclusive. When ChromaArrayType is equal to 0, pps_cb_qp_offset and pps_cr_qp_offset are not used in the decoding process and decoders shall ignore their value.
pps_slice_chroma_qp_offsets_present_flag equal to 1 indicates that the slice_cb_qp_offset and slice_cr_qp_offset syntax elements are present in the associated slice headers. pps_slice_chroma_qp_offsets_present_flag equal to 0 indicates that these syntax elements are not present in the associated slice headers. When ChromaArrayType is equal to 0, pps_slice_chroma_qp_offsets_present_flag shall be equal to 0.
chroma_qp_offset_list_enabled_flag equal to 1 specifies that the cu_chroma_qp_offset_flag may be present in the transform unit syntax. chroma_qp_offset_list_enabled_flag equal to 0 specifies that the cu_chroma_qp_offset_flag is not present in the transform unit syntax. When ChromaArrayType is equal to 0, it is a requirement of bitstream conformance that the value of chroma_qp_offset_list_enabled_flag shall be equal to 0.
diff_cu_chroma_qp_offset_depth specifies the difference between the luma coding tree block size and the minimum luma coding block size of coding units that convey cu_chroma_qp_offset_flag. The value of diff_cu_chroma_qp_offset_depth shall be in the range of 0 to log2_diff_max_min_luma_coding_block_size, inclusive. The variable Log2MinCuChromaQpOffsetSize is derived as follows:Log2MinCuChromaQpOffsetSize=CtbLog2SizeY−diff_cu_chroma_qp_offset_depth
chroma_qp_offset_list_len_minus1 plus 1 specifies the number of cb_qp_offset_list[i] and cr_qp_offset_list[i] syntax elements that are present in the PPS. The value of chroma_qp_offset_list_len_minus1 shall be in the range of 0 to 5, inclusive.
cb_qp_offset_list[i] and cr_qp_offset_list[i] specify offsets used in the derivation of Qp′Cb and Qp′Cr, respectively. The values of cb_qp_offset_list[i] and cr_qp_offset_list[i] shall be in the range of −12 to +12, inclusive.
It is desirable to improve the coding efficiency and/or syntax parsing throughput rate associated with palette index map coding.